package h0813;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 计算疫情扩散时间
 * @date 2024/8/13 14:59
 */
//TODO 要解决这个问题，可以使用广度优先搜索（BFS）算法。这种算法非常适合处理类似"蔓延"或"扩散"的问题，因为它会逐层遍历图中的节点。

public class InfectionSpread {
    // 用于表示四个方向：上，下，左，右
    private static final int[] DX = {-1, 1, 0, 0};
    private static final int[] DY = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        String[] input = scanner.nextLine().split(",");
//        int n = (int) Math.sqrt(input.length);
//        int[][] grid = new int[n][n];
        String[] input = scanner.nextLine().split(",");
        int n = (int) Math.sqrt(input.length);

        int[][] grid=new int[n][n];
        // 将输入的字符串转换为网格
        for (int i = 0; i < input.length; i++) {
            grid[i/n][i%n]=Integer.parseInt(input[i]);
        }

        int days = calculateDaysToInfect(grid, n);
        System.out.println(days);
    }

    public static int calculateDaysToInfect(int[][] grid, int n) {
        Queue<int[]> queue = new LinkedList<>();
        int totalCells = n * n;
        int infectedCount = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    //感染区域+1
                    infectedCount++;
                }
            }
        }
        //全部都感染，或者全部未感染
        if (infectedCount==totalCells||infectedCount==0){
            return -1;
        }
        int days=0;

        //进行bfs
        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] currentPos = queue.poll();
                int x = currentPos[0];
                int y = currentPos[1];
                for (int j = 0; j < 4; j++) {
                    int a = x + DX[j];
                    int b = y + DY[j];
                    //如何坐标合法且未感染，感染该区域
                    if (a >= 0 && a < n && b >= 0 && b < n && grid[a][b] == 0) {
                        grid[a][b]=1;
                        queue.offer(new int[]{a,b});
                        infectedCount++; //数量加一
                    }
                }
            }
            //经过一轮BFS就是一天

            if (!queue.isEmpty()){//如果此轮是最后一个节点poll出去后为空，则不能加一
                days++;
            }
        }
        return days;
    }
}

